from typing import List

MOD = 10 ** 9 + 7


class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        size = len(board)

        # 定义状态矩阵：dp[i][j] = [最大得分,方案数]
        dp = [[[0, 0] for _ in range(size)] for _ in range(size)]

        # 初始化状态矩阵
        dp[-1][-1] = [0, 1]

        for i in range(size - 2, -1, -1):
            if board[i][-1] != "X":
                dp[i][-1] = [dp[i + 1][-1][0] + int(board[i][-1]), dp[i + 1][-1][1]]
            else:
                break
        for j in range(size - 2, -1, -1):
            if board[-1][j] != "X":
                dp[-1][j] = [dp[-1][j + 1][0] + int(board[-1][j]), dp[-1][j + 1][1]]
            else:
                break

        for i in range(size - 2, -1, -1):
            for j in range(size - 2, -1, -1):
                board_num = int(board[i][j]) if board[i][j].isdigit() else 0
                if board[i][j] != "X":
                    max_val = max(dp[i + 1][j][0], dp[i][j + 1][0], dp[i + 1][j + 1][0])
                    max_num = sum([dp[i + 1][j][1] if dp[i + 1][j][0] == max_val else 0,
                                   dp[i][j + 1][1] if dp[i][j + 1][0] == max_val else 0,
                                   dp[i + 1][j + 1][1] if dp[i + 1][j + 1][0] == max_val else 0])
                    max_num %= MOD
                    dp[i][j] = [max_val + board_num, max_num]

        return dp[0][0] if dp[0][0][1] > 0 else [0, 0]


if __name__ == "__main__":
    # [7,1]
    print(Solution().pathsWithMaxScore(board=["E23",
                                              "2X2",
                                              "12S"]))

    # [4,2]
    print(Solution().pathsWithMaxScore(board=["E12",
                                              "1X1",
                                              "21S"]))

    # [0,0]
    print(Solution().pathsWithMaxScore(board=["E11",
                                              "XXX",
                                              "11S"]))
